Systems that communicate data using electromagnetic signals suffer from communication errors due to interference or noise. Interference often is produced by uncontrolled electromagnetic sources, while noise comes in many forms, including the random motion of electrons in the communication medium due to their thermal energy. Regardless the source of the errors, information that is transmitted often is not the same as the information received. Moreover, as the data rate of communications channels increases, they become less reliable due to these errors.
One technique developed to correct these communication errors is forward error correction, or “FEC”, also called channel coding. FEC works by having the transmitting device send redundant data, which the receiving device uses to correct errors. When data are sent continuously, for example as a stream of bits, FEC uses a “convolutional code” to determine the redundant data. Convolutional codes generate a parity bit by applying a carefully chosen binary polynomial to a sliding window of bits within a data stream. A recursive encoder adds the parity bit back to the data stream itself, while a non-recursive encoder provides the stream of parity data “out of band.” Such data streams may be decoded using the Viterbi algorithm, which is cost effective to implement in hardware due to the serial nature of the data processing.
When the data are sent in discrete groups, such as packets, then a “block code” is used. Block codes convert input messages having a fixed length (commonly called “k”) into code words having a longer length (“n”). The code words are carefully chosen so that when compared pairwise, they differ in at least a minimum number of positions; this number is the distance (“d”). Such codes can detect (d−1) errors, and can correct up to (d−1)/2 errors, rounded down. Well known block codes include Reed-Solomon codes, Golay codes, BCH codes, Hamming codes, and low-density parity-check (LDPC) codes.
Because redundant data are transmitted, FEC decreases the useful bandwidth of the communication medium. Therefore, there is a need to minimize the amount of redundant data to transmit. However, the amount of error between the transmitting device and the receiving device may change over time, so it is beneficial if the amount of redundant data similarly changes over time. It is known in the art to perform dynamic FEC on a stream of bits using a convolutional or Viterbi encoder and decoder; for example, see U.S. Pat. No. 6,128763 to LoGalbo et al. It is also known in the art to perform static (i.e., “on-or-off”) FEC at the block level; for example, see Institute of Electrical and Electronics Engineers (IEEE) Standard for 10 gigabit Ethernet over twisted pair cables, IEEE 802.3an-2006, available at http://standards.ieee.org/about/get/802/802.3.html, which describes the use of an LDPC code. However, there remains a need to perform adaptive FEC at the packet level, rather than the bit level. For example, high performance computing (HPC) systems often send packets over very high speed data interconnects that are particularly susceptible to communication errors.